package Algorithm.search;

/**
 * 合成byte字符串
 * 题目简述：有个长度26的表示a-z每个字符数量的数组，用两个较小字符可以合成一个高一位的字符（例两个a可以合成一个b），
 * 问用该字符数组最多可合成多少个byte字符串
 */
public class ByteCombine {

    /**
     * 思路：先确定可能能合成的数量区间，再进行二分查找，检查字符数组能够合成mid个byte字符串（先扣掉mid个byte字符，再逐个字符来看能否补齐）
     * ，最终确定能合成的最大数量。
     */
    int byteCombine(int[] count) {
        //[0, left)为可合成数量区间，(right, +无穷]为不可合成数量区间
        int left = 1, right = count[0]/2 + count[1]; //最大可合成数即为b的最大数量count[0]/2 + count[1]
        while (left <= right) { //二分查找更新区间
            int mid = (left + right) / 2;
            if (check(count, mid)) 
                left = mid + 1; //若可合成mid个，则继续向右移动left
            else 
                right = mid - 1; //否则向左移动right
        }
        return right; //此时left > right。根据区间定义返回right
    }

    /**
     * 检查字符数组能够合成n个byte字符串：先扣掉n个byte字符，再逐个字符来看能否补齐
     */
    boolean check(int[] count, int n) {
        int[] pairs = new int[26];
        for (int i = 0;i < 26;i++) {
            pairs[i] = count[i];
        }
        pairs['b' - 'a'] -= n;
        pairs['y' - 'a'] -= n;
        pairs['t' - 'a'] -= n;
        pairs['e' - 'a'] -= n;

        for (int i = 1;i < 26;i++) {
            pairs[i] += pairs[i-1]/2; //最大值也不会超过2*10^9，不会越界
            if (pairs[i] < 0) //小于0则说明无法用前面的字符补齐，不能满足合成
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new ByteCombine().byteCombine(new int[]{2, 1, 0, 4, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0}));
    }

}
